package me.timlong.StringDynamic;

public class SubSequenceNumber {
    /**
     * 题目描述
     * 给定一个字符串S和一个字符串T，计算S中的T的不同子序列的个数。
     * 字符串的子序列是由原来的字符串删除一些字符（也可以不删除）在不改变相对位置的情况下的剩余字符（例如，"ACE"is a subsequence of"ABCDE"但是"AEC"不是）
     * 例如：
     * S ="rabbbit", T ="rabbit"
     * 返回3
     *
     * 解决方案：
     *
     * 动态规划
     * f(i, j) -> s[0...i-1] 包含 t[0...j-1]的不同子序列个数
     * 初始化：
     * f(i, 0) = 1, (i = 0~s.length - 1), s串包含空串t的个数为1
     * f(0, j) = 0. (j = 1~t.length - 1), 空串s中包串t的个数为0
     *
     *
     * 递推方程:
     * 1、s[i-1] != t[j-1]时，则与字符串s[0...j-2]包含t[0...j-1]的个数相同，有f(i, j) = f(i-1, j)
     * 2、s[i-1] == t[j-1]时，则f(i, j)等于s[0...i-2]包含t[0...j-2]与s[0...i-2]包含t[0...j-1]个数的和
     *    即有f(i, j) = f(i-1, j-1) + f(i-1, j)
     */

    public int numDistinct(String S, String T) {

        int sLen = S.length();
        int tLen = T.length();


        int[][] dp = new int[sLen + 1][tLen + 1];

        // initialize
        for (int i = 0; i < sLen; i++)
            dp[i][0] = 1;
        for (int j = 1; j < tLen; j++)
            dp[0][j] = 0;

        for (int i = 0; i < sLen; i++)
            for (int j = 0; j < tLen; j++) {
                if(S.charAt(i) != T.charAt(j))
                    dp[i + 1][j + 1] = dp[i][j + 1];
                else
                    dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
            }

        return dp[sLen][tLen];
    }

    public static void main(String[] args) {
        String S ="rabbrarabit";
        String T ="ra";

        System.out.println(new SubSequenceNumber().numDistinct(S, T));
    }
}
